第1回 zk部
9/28 19:00~
参考文献のQAPらへんまで
ゴール
Flatting→QAPまでの流れ理解する = プログラムから多項式を作る！
zk-SNARKsでは何を証明しているのか
証明者が検証者に対して何かを証明できる証明システム
プログラムを証明システムによって証明できる何かに変換またはコンパイルする機能
ゼロ知識証明で中心となる考え方は根を持つ多項式$ f(x) を知っていることを証明するということ。
根は多項式で0に評価される値で、たとえば1とか2を根とする多項式を考えるとある多項式$ h(x)を考えたときに次のように表せる。
$ f(x) = (x-1)(x-2)h(x)
証明者は目的の多項式$ t(x) = (x-1)(x-2)について、$ f(x) =t(x)h(x)となるような$ f(x)と$ h(x)を知っていることを証明しなければならない。この例において、検証者がチェックしたい根は1と2になる。
つまり多項式を知っていることを証明する。ポイントはプログラムを多項式にするところ。結局多項式にできれば上記のフローは実現できる。
$ f(x)を明かさずにこれを証明するために使われる技法
準同型コミットメント
双線型性ペアリング
異なる多項式はほとんどの場合異なる値に評価されるという性質
証明の一部を隠す準同型コミットメントとその改良の双線型性ペアリング
証明者に送る値を隠す技法で、検証者が証明を検証できるようにしたい。
$ commitment(f(x)) = commitment(t(x))commitment(h(x)) = commitment(t(x)h(x))
準同型コミットメントを使うことで、相手に値を隠したまま渡すことができ、検証ができる。値が$ vとすると、$ pを法とするコミットメント$ g^vを送信すれば同一性のチェック等ができるようになる。(離散対数問題)
このコミットメントだと乗算チェックができない($ g^ag^b = g^{a+b}となり、加算のみのチェックしかできない)が、ペアリングを使えば$ e(g^a,g^b) = e(g,g)^{ab}となり乗算チェックができるようになる。
これで値を隠したまま、検証者が検証できる数学的な土台が出来上がる。
何が簡潔なの？(Succint)
2つの関数を評価するとほとんどの場合異なる値に評価されるという性質が由来。もう少し深ぼると、この2つの関数というのは先ほど出てた$ f(x)と$ t(x)h(x)と思ってもらって大丈夫。ランダムな点$ rでこの2つの関数を評価すると、ほとんどの場合、同じ結果は返されない。
ほんと？←ほんとです。(シュワルツ-ジッペルの補題として知られる概念で、次数$ n の2種類の多項式は最大$ n個の点で交わる)
確率的に無視できるほど小さな確率でしか等しくならないということはそれで証明すれば良い。群における点を比較することによってそれより大きい多項式を比較するのと同じことになる。(ただこれはトラステッドセットアップが必要な理由でもある)
等式のチェックに使われるランダムな点$ rがわかっていれば、証明者は有効な多項式を捏造して検証することができちゃうから。
トラステッドセットアップってなんですか？トラステッドのセットアップです。以下の手順を踏みます
1. ランダムな値$ rを生成する
2. $ rのいろいろな冪乗($ g,g^r,g^{r^2},g^{r^3}...)をコミットして証明者が点$ rについて知らないまま多項式を計算するときに使えるようにする
3. 値$ rを破棄する
証明者としての多項式が$ f(x) = 3x^2 + x + 2だとすると、$ (g^{r^2})^3 g^r g^2を計算してランダムな点$ rで評価された多項式のコミットメントを取得できる。
プログラムから多項式へ
証明者が求めなければならない多項式の制約は根がある事だったけど、一般的なステートメントについて考える。zk-SNARKsで応用されてるやつはこんな感じ？
値が[ $ 0,2^{64}] の範囲にあることを証明する(いわゆる範囲証明)
秘密の値が一定のマークルツリーに入っていることを証明する(zkRollupとかTornado cashとか？)
いくつかの値の和が他のいくつかの値の和に等しいことを証明する
プログラムの実行を多項式へ変換しないといけない(数学的な問題に帰着させる必要がある)が、大雑把には以下の手順を踏む
1. プログラムを演算回路に変換する
2. その演算回路を特定の等式のシステム(行列)に変換する(R1CS)
3. 等式システムを多項式に変換する
大前提として、↑の処理をするわけだからプログラムは数学で書き表すことができるという前提がある。簡単に例を見ると
code:rust
fn my_function(w,a,b){
if(w == true){
return a * (b + 3)
}else{
return a + b
}
}
このプログラムは次の等式を使えば数学で書き直せる。
$ w \times (a \times (b + 3)) + (1-w)\times (a+b) = v
$ vが出力で$ wは0 or 1になる。
これを一連の制約に変換する。zkSNARKで必要なのはランク1制約システム(R1CS)で$ L \times R = Oという形の一連の等式で、$ L ,R,Oはそれぞれ変数の加算にしかならないので$ L,Rに限られる。先ほどのやつに対して適応すると以下のようになる
$ a \times (b + 3) = m
$ w \times (m - a - b) = v - a -b
$ w \times w = w
この変換がR1CSの認識。あってます？R1CSの作業はこの後の処理を簡単にするためみたいな認識
R1CSで制約を追加できたので、これをもとに多項式に変換していく。
まずは単純に多項式を作ってみる(これはただのイメージなので実際に行われてる処理じゃないです)
例えば根を1,2,3とかを持つ多項式を考えると
$ f(1) = a \times (b + 3) - m
$ f(2) = w \times (m - a - b) - (v - a -b)
$ f(3) = w \times w - w
正しい入力が与えられた場合のみ、上記の式は全て0として評価される(1,2,3を根として持つ)
ただ、これだと明らかに問題がある(ない)(根がわかっている状態なのでそれように多項式を作ればいいだけ。今回だと1,2,3って勝手に定義してる)
→動的に多項式を作れるようにすればいい。(FFTを使うため)
そんなことできるの？←できる。ラグランジュ補間のアルゴリズムを使用する。大雑把に言えば、座標から多項式を作る手法
$ f(x) =\lambda _1(x)f(i_1)+\cdots +\lambda _k(x)f(i_k)\bmod p
$ \lambda_j(x)=\frac{(x-i_1)\cdots(x-i_k)}{(i_j-i_1)\cdots(i_j-i_k)}\bmod p
$ \lambda_j(x_i) = \delta_{i,j}
例えば$ (1,2)(2,4)(3,7)を通る二次関数を作ろうとすると以下のようになる
https://scrapbox.io/files/6333ba2ce52cc00023eb894f.png
$ x = 1を代入すると他の部分が全部0になっていることを利用する。
先ほどの等式$ f(1) = a\times(b+3)-mを以下のように変更する
$ f_1(x) = aL_1(x) \times (b+3)R_1(x) - mO_1(x)
$ L_1(1) = R_1(1) = O_1(1) = 1
$ L_2(2) = R_2(2) = O_2(2) = 1
$ f_1(x) = L_1(x) \times R_1(x) - O_1(x)
$ L_1(x) = av_a(x), R_1(x)=bv_b(x) + 3v_0(x), O_1(x) = mv_m(x)
$ x=1の時のみ$ a\times(b+3)-mと評価され、それ以外の値の時は0として評価される。
結果的な等式として$ f(x) = f_1(x) + f_2(x) + f_3(x)が得られる。
実際に
$ f(1) = f_1(1) + f_2(1) + f_3(1) = f_1(1) + 0 + 0 = aL_1(1) \times (b+3)R_1(1) - mO_1(1) = a \times (b+3) - m
と得ることができる。
等式をこのように新しく表すことで証明者は多項式のうち自分に関係する部分だけを評価できるようになる。($ aは秘密の値、$ mは中間値の値)
1. 指数に隠されているランダムな点$ rの冪乗をとって、多項式$ L_1(r)と$ O_1(r)を再構築する
2. $ g^{L_1(r)}を秘密の値で冪乗して$ (g^{L_1(r)})^a = g^{L_1(r)a}を得る。これは未知のランダムな点$ x = rで評価されて指数に隠された$ a \times L_1(x)を表す。
3. $ g^{O_1*(r)}を秘密の中間値$ mで冪乗して$ (g^{O_1(r)})^m = g^{mO_1(r)}を得る。これはランダムな点$ rでの$ mO_1(x)の評価を表して指数に隠される。
検証者は次に合意された値$ bについて$ (g^{R_1(r)})^b,(g^{R_1(r)})^3を再構築することでかけてる部分を埋める。
この2つを加算すると$ g^{bR_1(r)} + g^{3R_1(r)}が得られ、これは未知のランダムな点$ x =rにおける$ (b+3) \times R_1(x)の評価を表す。
最終的に検証者は$ f_1(r)を再構築し、これが双線型性ペアリングを用いて指数に隠される
$ e(g^{aL_1(r)},g^{(b+3)R_1(r)}) - e(g,g^{mO_1(r)}) = e(g,g)^{aL_1(r) \times (b+3)R_1(r) - mO_1(r)}
これらの手法を補完して多項式を完成すると最終的なプロトコルを求めることができる。
QAPとは演算処理の多項式への変換
今までやってきたことをまとめると、
1. プログラムを数式に変換する
2. 数式をランク1制約システムに則って変換する
3. 変換したものを動的にラグランジュ補間アルゴリズムを使って多項式を作る
プログラムを数式に変換する→Flatting
数式を算術回路に落とし込む→R1CS
変換したもので多項式を作る→QAP
疑問コーナー
証明者は多項式を作るところまではやってない？必要な部分のみを構築して正確には検証者が多項式を作る？(その間でTrusted Setupが入る？)
数式→R1CSの時の変換が、よく見る論理ゲートの図でやってることに近い？
得られたもの
Kateの発音について
参考文献
ゼロ知識証明入門